package com.sicheng.lc.周赛.分类.图论;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/11 15:20
 */
public class 所有可能的路径 {
    //https://leetcode.cn/problems/all-paths-from-source-to-target/
    public List<List<Integer>> allPathsSourceTarget(int[][] g) {
        int n = g.length;
        ArrayDeque<Node> q = new ArrayDeque<>();
        ArrayList<Integer> fir = new ArrayList<>();
        ArrayList<List<Integer>> res = new ArrayList<>();
        fir.add(0);
        q.offer(new Node(fir, 0));
        while (!q.isEmpty()) {

            Node node = q.poll();
            int x = node.p;
            List<Integer> path = node.path;
            if (x == n - 1) {
                res.add(path);
                continue;
            }

            for (int y : g[x]) {
                ArrayList<Integer> newPath = new ArrayList<>(path);
                newPath.add(y);
                q.offer(new Node(newPath, y));
            }
        }

        return res;

    }

    class Node {
        List<Integer> path;
        int p;

        public Node(List<Integer> path, int p) {
            this.path = path;
            this.p = p;
        }
    }
}
